// https://www.lintcode.com/problem/flood-fill/

public class Solution {
    protected int oldColor;
    
    /**
     * @param image: a 2-D array
     * @param sr: an integer
     * @param sc: an integer
     * @param newColor: an integer
     * @return: the modified image
     */
    public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
        // Write your code here
        oldColor = image[sr][sc];
        _floodFill(image, sr, sc, newColor);
        return image;
    }
    
    protected void _floodFill(int[][] image, int sr, int sc, int newColor) {
        image[sr][sc] = newColor;
        for (int dir = 0; dir < 4; ++dir) {
            int[] r = canGo(image, sr, sc, dir);
            if (r.length > 0) {
                _floodFill(image, r[0], r[1], newColor);
            }
        }
    }
    
    protected int[] canGo(int[][] image, int sr, int sc, int dir) {
        int nr = sr, nc = sc;
        if (dir == 0) { // 上
            --nr;
        } else if (dir == 1) { // 下
            ++nr;
        } else if (dir == 2) { // 左
            --nc;
        } else { // 右
            ++nc;
        }
        boolean c1 = (nr >= 0) && (nr < image.length);
        boolean c2 = (nc >= 0) && (nc < image[0].length);
        if (c1 && c2) {
            if (image[nr][nc] == oldColor) {
                return new int[]{nr, nc};
            }
        }
        return new int[]{};
    }
}